package 数组和链表;

import java.util.Random;
import java.util.Stack;

public class SkipList<E extends Comparable<? super E>> {
    //概率因子
    private static final double UP_RATE = 0.5;//升级因子
    private final Stack<Node> stack = new Stack<Node>();
    private Node head;//整个跳表的开始节点

    public SkipList() {
        head = new Node(null);
    }

    public static void main(String[] args) {
        SkipList<Integer> skipList = new SkipList<>();
        Random random = new Random();
        int[] arr = {3, 7, 8, 9, 10, 11, 12, 13, 15, 17, 19, 20, 21, 22, 23, 24, 25,
                26, 27, 29, 30, 31, 32, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 46};
        for (int i : arr) {
            skipList.add(i);
        }
        skipList.print();
        skipList.search(3);

    }

    private Node findPredecessor(E value) {
        stack.clear();
        for (; ; ) {
            for (Node q = head, r = q.right, d; ; ) {
                if (r != null) {
                    if (((Comparable) value).compareTo(r.value) > 0) {
                        q = r; //大于当前节点，继续往右查找
                        r = r.right;
                        continue;
                    }
                }
                if ((d = q.down) == null) {
                    return q;//验证到最底层，返回最底层的节点
                }
                stack.push(q);//保存下沉时候的节点
                q = d;//下沉，继续验证下一层的节点
                r = d.right;
            }
        }
    }

    public Node search(E value) {
        if (value == null) {
            throw new NullPointerException();
        }
        Node preNode = findPredecessor(value);
        if (preNode.right == null) {
            return null;
        }
        if (((Comparable) value).compareTo(preNode.right.value) == 0) {
            return preNode;
        }
        return null;
    }

    public void add(E value) {
        if (value == null) {
            throw new NullPointerException();
        }
        Node preNode = findPredecessor(value);
        if (preNode.right != null && ((Comparable) value).compareTo(preNode.right.value) == 0) {
            return;
        }
        Node node = new Node(value);
        node.right = preNode.right;
        preNode.right = node;
        Random random = new Random();
        Node up;
        Node down;
        for (; ; ) {
            if (random.nextDouble() < UP_RATE) {
                break;
            }
            down = node;
            node = new Node(value); //初始化节点，并把底层节点加到节点的down属性上
            node.down = down;
            if (stack.isEmpty()) {//存放刚刚下沉的节点，如果stack为空，则随机升级成功
                Node newHead = new Node(null);
                newHead.down = head;
                newHead.right = node;
                head = newHead;
                break;
            }
            up = stack.pop();
            node.right = up.right;
            up.right = node;
        }
    }

    public void delete(E value) {
        if (value == null) {
            throw new NullPointerException();
        }
        Node preNode = findPredecessor(value);
        if (((Comparable) value).compareTo(preNode.right.value) != 0) {
            return;
        }
        for (; ; ) {
            if (preNode.right == null || ((Comparable) value).compareTo(preNode.right.value) != 0) {
                break;
            }
            preNode.right = preNode.right.right;
            if (head.right == null && head.down != null) {
                head = head.down;
            }
            if (stack.isEmpty()) {
                break;
            }
            preNode = stack.pop();
        }
    }

    public void print() {
        for (Node c = head; ; ) {
            for (Node r = c.right; ; ) {
                if (r == null) {
                    System.out.println();
                    break;
                }
                System.out.print(r.value + ",");
                r = r.right;
            }
            if (c.down == null) {
                break;
            }
            c = c.down;
        }
    }

    public class Node<E extends Comparable<? super E>> {
        public E value;
        public Node down, right;

        public Node(E value) {
            this.value = value;
        }
    }

} 